import java.util.*;
import java.util.function.Consumer;

public class Main {

    public static void main(String[] args) {
        BinarySortTree tree = new BinarySortTree();
        int[] arr = {7, 3, 10, 1, 5, 2, 9, 12,};
        for (int i = 0; i < arr.length; i++) {
            tree.add(new Node(arr[i]));
        }
//        tree.add(new Node(9));
        tree.midOrder();

    }


    static class BinarySortTree {
        private Node root;

        public void add(Node node) {
            if (root == null) root = node;
            else root.add(node);
        }

        public void midOrder() {
            if (root == null) System.out.println("树为空，不能遍历");
            else root.midOrder();
        }

        public Node findNode(int value) {
            return root.findNode(value);
        }

    }

    static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
            left = null;
            right = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }

        public void add(Node node) {
            if (node == null) return;
            if (node.value < this.value) {
                if (this.left == null) this.left = node;
                else this.left.add(node);
            } else if (node.value > this.value) {
                if (this.right == null) this.right = node;
                else this.right.add(node);
            } else {
                System.out.println(node.toString() + "已经存在，不能插入！");
            }
        }

        public void midOrder() {
            if (this.left != null) this.left.midOrder();
            if (this.right != null) this.right.midOrder();
            System.out.println(this);
        }


        public Node findNode(int value) {
            if (this == null) {
                System.out.println("未找到！");
                return null;
            }
            if (value == this.value) return this;
            else if (value < this.value) {
                if (this.left == null) {
                    System.out.println("未找到！");
                    return null;
                } else return this.left.findNode(value);
            } else {
                if (this.right == null) {
                    System.out.println("未找到！");
                    return null;
                } else return this.right.findNode(value);
            }
        }


    }
}

